package BinomialHeap;

/**
 * BinomialHeap
 *
 * An implementation of binomial heap over non-negative integers.
 * Based on exercise from previous semester.
 */
public class BinomialHeap
{
	private HeapNode min = null;//points to node containing the minimal element in the heap.
	private HeapNode lowestRankRoot = null;//points to the root of the tree with the lowest rank.
	private HeapNode highestRankRoot = null;//points to the root of the tree with the highest rank.
	private int size = 0;//number of nodes in the tree.
	public static int linkCounter = 0;//counts how many times two trees were linked. used for assignment.
	
	
	public int[] treesSize() {//method for test, will delete later
		int treeNum=0;
		HeapNode curr = lowestRankRoot;
		while (curr!=null) {
			treeNum++;
			curr = curr.getLeftBrother();
		}
		int[] treeSizes = new int[treeNum];
		curr = lowestRankRoot;
		for(int i=0;i<treeNum;i++){
			treeSizes[i] = (int)Math.pow(2, curr.getRank());
			curr = curr.getLeftBrother();
		}
		return treeSizes;
	}
	
	public boolean contains(int i) {//method for test, will delete later
		HeapNode curr = highestRankRoot;
		while (curr != null) {
			if (contains(curr, i))
				return true;
			curr = curr.getRightBrother();
		}
		return false;
		
	}
	
	private boolean contains(HeapNode node, int i) {//method for test, will delete later
		if (node == null)
			return false;
		if (node.getValue() == i)
			return true;
		HeapNode curr = node.getLeftMostSon();
		while (curr != null) {
			if (contains(curr, i))
				return true;
			curr = curr.getRightBrother();
		}
		return false;
	}
	
	/**
	 * Constructor 1 - creates a new binomial heap with a single node, whose value is rootValue.
	 *
	 * Complexity - O(1)
	 */
	BinomialHeap(int rootValue) {
		this.min = new HeapNode(rootValue);
		this.lowestRankRoot = this.min;
		this.highestRankRoot = this.min;
		this.size = 1;
	}

	/**
	 * Constructor 2 - creates a new empty binomial heap.
	 * 
	 * Complexity - O(1)
	 */
	public BinomialHeap() {
	}

/**
    * public boolean empty()
    *
    * precondition: none
    * 
    * The method returns true if and only if the heap
    * is empty.
    * 
    * Complexity - O(1)
    *   
    */
    public boolean empty()
    {
    	return min==null;
    }
    
		
   /**
    * public void insert(int value)
    *
    * Insert value into the heap 
    * 
    * worst case complexity - O(logn), cmortized complexity - O(1).
    * 
    * Similar to binary counter increment where worst case is O(logn).
    * 
    */
    public void insert(int value) 
    {    
    	BinomialHeap newHeap = new BinomialHeap(value); //Create a new binomial heap with one item
    	this.meld(newHeap); //meld this binomial heap with newHeap
    }

   /**
    * public void deleteMin()
    *
    * Delete the minimum value:
    * 1. Remove the minimum root and its children from this heap and update the 'lowestRankRoot' 
    * 	 and 'HighestRankRoot' fields of this heap (O(1)).
    * 2. Update the 'min' field of this heap (O(log(n))).
    * 3. Create a new temporary heap 'sonsHeap', set its 'highestRankRoot'
    *    as deleted root's leftmost child (O(1)).
    * 4. Update the fields 'min', 'lowestRankRoot' and 'size' in 'sonsHeap' (O(log(n)).
    * 5. Update the field 'size' of this heap (O(1)).
    * 6. Meld this heap with 'sonsHeap' (O(log(n)).
    * 
    * Complexity - O(logn)
    *
    */
    public void deleteMin()
    {
    	if (min == null)
    		return;
    	
     	HeapNode deletedMin = this.min; //extract minimum
     	
     	// 1. Remove the minimum root and its children from this heap and update the 'lowestRankRoot' 
        // 	  and 'HighestRankRoot' fields of this heap (O(1)):
     	
     	if (min.getRightBrother() == null && min.getLeftBrother() == null) { //this heap has only one root
     		highestRankRoot = null;
     		lowestRankRoot = null;
     		min = null;
     	} else if (min.getRightBrother() == null) { //min is the current lowestRankRoot.
     		lowestRankRoot = min.getLeftBrother();
     		lowestRankRoot.setRightBrother(null);
     	} else if (min.getLeftBrother() == null) { //min is the current highestRankRoot.
     		highestRankRoot = min.getRightBrother();
     		highestRankRoot.setLeftBrother(null);
     	} else { //min is in the middle of the root list, i.e, it has right and left brothers.
     		min.getLeftBrother().setRightBrother(min.getRightBrother());
     		min.getRightBrother().setLeftBrother(min.getLeftBrother());
     	}
     	
     	// 2. Update the 'min' field of this heap (O(log(n))):
     	
     	setMin();
     	
     	// 3. Create a new temporary heap 'sonsHeap', set its 'highestRankRoot'
     	//    as deleted root's leftmost child (O(1)):

     	BinomialHeap sonsHeap = new BinomialHeap ();
     	sonsHeap.setHighestRankRoot(deletedMin.getLeftMostSon());
     	
     	// 4. Update the fields 'min', 'lowestRankRoot' and 'size' in 'sonsHeap' (O(log(n)):
     	
     	HeapNode tempMin = deletedMin.getLeftMostSon();//the root with the minimal value so far
     	HeapNode currentRoot = deletedMin.getLeftMostSon();//running root
     	HeapNode tempLowestRankRoot = deletedMin.getLeftMostSon();//the root with the minimal rank so far
     	int sizeFactor = 0;//used to calculate the size of 'sonsHeap'. it is the number of children of deletedMin.
     	
     	while (currentRoot != null) { /*search for the lowest rank root, find the minimum and calculate 
     								    sizeFactor on the way.*/
     		currentRoot.setParent(null);
     		if (currentRoot.getValue() < tempMin.getValue()) {
     			tempMin = currentRoot;
     		}
     		tempLowestRankRoot = currentRoot;
     		currentRoot = currentRoot.getRightBrother();
     		sizeFactor++;
     	}
     	if (tempMin != null)//set 'isMin' flag
     		tempMin.isMin = true;
     	sonsHeap.setLowestRankRoot(tempLowestRankRoot);
     	sonsHeap.setMin(tempMin);
     	sonsHeap.setSize((int) (Math.pow(2, sizeFactor)-1));
     	
     	// 5. Update the field 'size' of this heap (O(1)):
     	
     	setSize(size-sonsHeap.getSize()-1);
     	
     	// 6. Meld this heap with 'sonsHeap' (O(log(n)):
     	
     	this.meld(sonsHeap); //meld this heap with deletedMin's sons heap
    }

    /** 
     * returns heap's size. complexity: O(1).
     */
    private int getSize() {
		return size;
    }

	/**
     * Sets heap's size to be the input value. complexity: O(1).
     */
    private void setSize(int newSize) {
    	size = newSize;
    }

	/**
     * Sets the input HeadNode to be the min root. complexity: O(1).
     */
    private void setMin(HeapNode node) {
    	min = node;
    }

	/**
     * Sets the input HeapNode to be the lowestRankRoot. complexity: O(1).
     * 
     */
    private void setLowestRankRoot(HeapNode node) {
    	lowestRankRoot = node;
    }

	/**
     * Sets the input HeapNode to be the highestRankRoot. complexity: O(1).
     * 
     */
    private void setHighestRankRoot(HeapNode node) {
    	highestRankRoot = node;
    }

	/**
     * Searches for the current minimum root and points 'min' to it.
     * 
     * Complexity - O(log(n))
     * Check all roots (There are log(n) roots) and find the smallest one
     */
   private void setMin() {
	   if (lowestRankRoot == null)
		   return;
	   min = lowestRankRoot;//start with lowest rank and move left.
	   HeapNode current = lowestRankRoot.getLeftBrother();
	   while (current != null) {
		   if (current.getValue() < min.getValue()) {
			   min = current;
		   }
		   current = current.getLeftBrother();
	   }
	   if (min != null)
		   min.isMin = true;
   }

   /**
    * public int findMin()
    *
    * Return the minimum value
    * 
    * complexity: O(1).
    *
    */
    public int findMin()
    {
    	if (min == null)
    		return -1;
    	return min.value;
    } 
    
   /**
    * public void meld (BinomialHeap heap2)
    *
    * Meld the heap with heap2.
    * 
    * complexity: O(log(n)):
    * in order to meld the two heaps, we will have to at least go over all the roots of one of the heaps,
    * and at most go over all the roots of both heaps.
    * 
    *
    */
    public void meld (BinomialHeap heap2)
    {
    	
    	if (heap2 == null || heap2.min == null)
    		return;
    	
    	/**a temporary heap to which we will add new roots during the meld.
		   after all roots are added the meld is over, and this heap's HeapNode fields are set as
    	   the temporary heap's HeapNode fields:*/
    	BinomialHeap tempHeap = new BinomialHeap();
    	
    	//auxiliary nodes:
    	HeapNode tempNode = null;
    	HeapNode tempNode1 = null;
    	HeapNode thisCurrentRoot = this.lowestRankRoot;//running root of this heap
    	HeapNode otherCurrentRoot = heap2.lowestRankRoot;//running root of heap2
    	HeapNode carry = null;
    	
    	
    	/**the new minimum will either be the minimum of this heap or the minimum of heap2,
    	   so find it now and set the 'isMin' flags accordingly:*/
    	if (findMin() == -1) {//this heap is empty
    		tempHeap.min = heap2.min;//the minimum after the meld will be the minimum of heap2
    		tempHeap.min.isMin = true;//make sure isMin is true
    	}
    	else if (findMin() > heap2.findMin()) {//the minimum of heap2 is smaller than the minimum of this heap
    		min.isMin = false;//the minimum of this heap loses its status as a minimum
    		tempHeap.min = heap2.min;//the minimum after the meld will be the minimum of heap2
    		tempHeap.min.isMin = true;//make sure isMin is true
    	}
    	else {//the minimum of heap2 is not smaller than the minimum of this heap
    		min.isMin = true;//make sure isMin is true
    		heap2.min.isMin = false;//the minimum of heap2 loses its status as a minimum
    		tempHeap.min = min;//the minimum after the meld will be the minimum of this heap
    	}
    	
    	/**the main loop - build the temporary heap by melding this heap and heap2:*/
    	while (!(carry == null && thisCurrentRoot == null && otherCurrentRoot == null)) {
    		
    		/**we're not carrying a root from the previous round:*/
    		if (carry == null) {
    			
    			/**there are no more roots in this heap:*/
        		if (thisCurrentRoot == null) {
        			tempHeap.concatenate(otherCurrentRoot); //Concatenate the remaining roots of heap2 to tempHeap
        			tempHeap.highestRankRoot = heap2.highestRankRoot;
        			otherCurrentRoot = null; //set otherCurrentRoot to null in order to end the while loop
        		} 
        		
        		/**there are no more roots in heap2:*/
        		else if (otherCurrentRoot == null) {
        			tempHeap.concatenate(thisCurrentRoot); //Concatenate the remaining roots of this heap to tempHeap
        			tempHeap.highestRankRoot = highestRankRoot;
        			thisCurrentRoot = null; //set thisCurrentRoot to null in order to end the while loop
        		} 
        		
        		/**running root of this heap has lower rank than running root of heap2:*/
        		else if (thisCurrentRoot.getRank() < otherCurrentRoot.getRank()) {
        			tempNode = thisCurrentRoot;//save running root of this heap in order to move it to tempHeap
        			thisCurrentRoot = thisCurrentRoot.getLeftBrother();//advance running root of this heap
        			tempHeap.addRoot(tempNode);//add saved root to tempHeap
        		} 
        		
        		/**running root of heap2 has lower rank than running root of this heap:*/
        		else if (thisCurrentRoot.getRank() > otherCurrentRoot.getRank()) {
        			tempNode = otherCurrentRoot;//save running root of heap2 in order to move it to tempHeap
        			otherCurrentRoot = otherCurrentRoot.getLeftBrother();//advance running root of heap2
        			tempHeap.addRoot(tempNode);//add saved root to tempHeap
        		} 
        		
        		/**running roots of heap2 and this heap have equal ranks:*/
        		else if (thisCurrentRoot.getRank() == otherCurrentRoot.getRank()) {
        			tempNode = thisCurrentRoot;//save running root of this heap
        			tempNode1 = otherCurrentRoot;//save running root of heap2
        			thisCurrentRoot = thisCurrentRoot.getLeftBrother();//advance running root of this heap
        			otherCurrentRoot = otherCurrentRoot.getLeftBrother();//advance running root of heap2
        			carry = tempNode.link(tempNode1);//link saved roots and set the result as carry
        		}
        		
    		} 
    		
    		/**we're carrying a root from the previous round:*/
    		else {
    			
    			/**running root of this heap is null or has a rank different (bigger) than carry's rank, and
    			   running root of heap2 is null or has a rank different (bigger) than carry's rank:*/
    			if ((thisCurrentRoot == null || !(thisCurrentRoot.getRank() == carry.getRank()))
    					&& ((otherCurrentRoot == null || !(otherCurrentRoot.getRank() == carry.getRank())))) {
    				
    				tempHeap.addRoot(carry);//add carry to tempHeap
    				carry = null;
    			} 
    			
    			/**running root of this heap is equal to carry's rank and
    			   running root of heap2 is null or has a rank different (bigger) than carry's rank:*/
    			else if (!(thisCurrentRoot == null) && (carry.getRank() == thisCurrentRoot.getRank()
    					&& (otherCurrentRoot == null || !(carry.getRank() == otherCurrentRoot.getRank())))) {
    						
    					tempNode = thisCurrentRoot;//save running root of this heap in order to link it with carry
    					thisCurrentRoot = thisCurrentRoot.getLeftBrother();//advance running root of this heap
    					carry = carry.link(tempNode);//link carry with saved root and set the result as carry
    			}
    			
    			/**running root of heap2 is equal to carry's rank and
    			   running root of this heap is null or has a rank different (bigger) than carry's rank:*/
    			else if (!(otherCurrentRoot == null) && (carry.getRank() == otherCurrentRoot.getRank()
    					&& (thisCurrentRoot == null || !(carry.getRank() == thisCurrentRoot.getRank())))) {
    					
    					tempNode = otherCurrentRoot;//save running root of heap2 in order to link it with carry
    					otherCurrentRoot = otherCurrentRoot.getLeftBrother();//advance running root of heap2
						carry = carry.link(tempNode);//link carry with saved root and set the result as carry
    			} 
    			
    			/**running root of this heap is equal to carry's rank and
    			   running root of heap2 is equal to carry's rank:*/
    			else if (carry.getRank() == thisCurrentRoot.getRank()
    					&& carry.getRank() == otherCurrentRoot.getRank()) {
    				
    				tempHeap.addRoot(carry);//add carry to tempHeap
    				tempNode = thisCurrentRoot;//save running root of this heap
    				tempNode1 = otherCurrentRoot;//save running root of heap2
    				thisCurrentRoot = thisCurrentRoot.getLeftBrother();//advance running root of this heap
    				otherCurrentRoot = otherCurrentRoot.getLeftBrother();//advance running root of heap2
    				carry = tempNode.link(tempNode1);//link saved roots and set the result as carry
    			}
    		}
    	}
    	
    	//update all HeapNode fields of this heap to the HeapNode fields of the temporary heap:
    	min = tempHeap.min;
    	lowestRankRoot = tempHeap.lowestRankRoot;
    	highestRankRoot = tempHeap.highestRankRoot;
    	
    	size+=heap2.size(); //increase this heap's size by adding heap2's size to it.
    }
    
    /** 
     * removes 'node' from its previous heap and adds it as the leftmost root of this heap.
     * highestRankRoot is pointed to 'node'.
     * if this heap is currently empty, lowestRankRoot is pointed to 'node'.
     * 
     * complexity: O(1).
     */
    private void addRoot(HeapNode node) {
    	node.rightBrother = null;
    	node.leftBrother = null;
    	if (lowestRankRoot == null) {
    		lowestRankRoot = node;
    		highestRankRoot = node;
    		return;
    	}
    	node.rightBrother = highestRankRoot;
    	highestRankRoot.leftBrother = node;
    	highestRankRoot = node;
}

/**
    * public int size()
    *
    * Return the number of elements in the heap
    * 
    * complexity: O(1).
    *   
    */
    public int size()
    {
    	return size;
    }
    
   /**
    * public int minTreeRank()
    *
    * Return the minimum rank of a tree in the heap.
    * 
    * complexity: O(1).
    * 
    */
    public int minTreeRank()
    {
        if (lowestRankRoot == null)
        	return -1;
    	return lowestRankRoot.getRank();
    }
	
   /**
    * public boolean[] binaryRep()
    *
    * Return an array containing the binary representation of the heap.
    * 
    * Complexity - O(log(n))
    * Going over all the roots once, there are O(logn) roots.
    * 
    */
    public boolean[] binaryRep()
    {
    	if (highestRankRoot == null)
    		return new boolean[0];
		boolean[] arr = new boolean[highestRankRoot.getRank()+1];
		HeapNode current = lowestRankRoot;
        while (current != null) {
        	arr[current.getRank()] = true;
        	current = current.getLeftBrother();
        }
        return arr;
    }

   /**
    * public void arrayToHeap()
    *
    * Insert the array to the heap. Delete previous elements in the heap.
    * 
    * Complexity - O(n)
    * n inserts, each is amortized O(1).
    * 
    */
    public void arrayToHeap(int[] array)
    {
        //'reset' the heap's attributes
    	min = null;
        lowestRankRoot = null;
        highestRankRoot = null;
        size = 0;
        
        //insert all the elements in the array
        for (int num : array) {
        	insert(num);
        }
    }
	
   /**
    * public boolean isValid()
    *
    * Returns true if and only if the heap is valid.
    * a heap is valid if and only if every element in it is a valid binomial tree, and the rank of every binomial
    * tree in the heap is bigger than the rank of its right brother (if it has one).
    * 
    * complexity: O(n). iterates on the roots. each iteration performs O(1) steps + calls rankAndCheck on the root. 
    * rankAndCheck's run time is linearly correlated with the root's number of descendants, i.e. performs O(1) steps
    * for each descendant.
    * 
    * in total, O(1) steps are performed for each node in the heap, and O(n) are performed overall.
    *   
    */
    public boolean isValid() 
    {
    	HeapNode curr = lowestRankRoot;//a root that will run on all the roots, from lowest to highest rank
    	int treeRank;
    	int prevRank = -1;
    	
    	while (curr != null) {
    		//rankAndCheck(curr) returns the rank of curr if it is a valid binomial tree,
			//or -1 if it is not a valid binomial tree:
    		treeRank = rankAndCheck(curr);
    		
    		//in order for the heap to be valid each binomial tree must be valid;
    		//its rank must be non-negative and bigger than the rank of its right brother (if it has one):
    		if (treeRank <= prevRank)
    			return false;
    		
    		//advance the parameters:
    		prevRank = treeRank;
    		curr = curr.leftBrother;
    	}
    	return true;
    }
    
    
    /**
     *  returns the rank of the binomial tree whose root is 'node'.
     *  if 'node' is not a root of a valid binomial tree - returns -1.
     *  
     *  a node that has has k children is the root of a valid binomial tree of rank k if and only if:
     *  
     *  1. the leftmost son of the node is itself a root of a valid binomial tree of rank k-1.
     *  
     *  2. every other son of the node is itself a root of a valid binomial tree, whose rank is smaller by 1
     *     than the rank of its left brother.
     *     
     *  3. every node in the tree has a value not smaller than the value of its parent
     *  
     *  complexity: O(n), where n is the number of descendants of 'node'.
     *  the first 'while' counts the children of 'node'. each iteration performs O(1) steps.
     *  
     *  the second 'while' iterates on the children, each iteration performs O(1) steps + 
     *  calls rankAndCheck recursively on each child.
     *  
     *  in total, for every descendant of 'node' 2 iterations are performed: one to count it, the other to
     *  call rankAndCheck on it. so for every descendant O(1) steps are performed.
     */
    private int rankAndCheck(HeapNode node) {
    	int numOfChildren = 0;//will contain the number of node's children
    	HeapNode curr = node.getLeftMostSon();//a pointer that will run on all of node's children from left to right
    	
    	//count the number of node's children:
    	while (curr != null) {
    		numOfChildren++;
    		curr = curr.getRightBrother();
    	}
    	
    	//check if the children are valid binomialtrees of the expected rank:
    	
    	curr = node.getLeftMostSon();//a pointer that will run on all of node's children from left to right
    	int currRank = numOfChildren - 1;//contains the expected rank of curr in every iteration
    	
    	while (curr != null) {
    		
    		//if one of node's children isn't a valid binomial tree of the expected rank,
    		//or has a value smaller than node's - then node isn't a root of a valid binomial tree - so return -1
    		if (currRank != rankAndCheck(curr) || curr.getValue() < node.getValue())
    			return -1;
    		
    		//advance the parameters:
    		currRank--;
    		curr = curr.getRightBrother();
    	}
    	
    	return numOfChildren;
    }
    
    /**
	 * Concatenates HeapNode 'other' and all of its brothers on the left to this Heap.
	 * if this heap is empty - points lowestRankRoot to 'node'.
	 * 
	 * Complexity - O(1).
	 * 
	 */
	private void concatenate(HeapNode node) {
		if (node == null)
			return;
		if (lowestRankRoot == null) {
			lowestRankRoot = node;
			node.rightBrother = null;
			return;
		}
		highestRankRoot.leftBrother = node;
		node.rightBrother = highestRankRoot;
	}
    
   /**
    * public class HeapNode
    * 
    * If you wish to implement classes other than BinomialHeap
    * (for example HeapNode), do it in this file, not in 
    * another file 
    *  
    */
    public class HeapNode{
    	public int value;
    	public int rank = 0;
    	public HeapNode leftMostSon = null;
    	public HeapNode parent = null;
    	public HeapNode rightBrother = null;
    	public HeapNode leftBrother = null;
    	
    	//when performing a meld, the 'isMin' field helps us to be sure that the new minimum will be a node that is
    	//currently the minimum of one of the 2 heaps.
    	//the 'isMin' field of the smaller minimum will be set to 'true' and thus ensure it stays on top, not
    	//being made a child of a node that has the same value. this way, we don't have to search for a minimum.
    	public boolean isMin = false;
    	
    	/**
    	 * Constructor - creates a new HeapNode with the input value
    	 * 
    	 * Complexity - O(1)
    	 */
    	HeapNode (int value) {
    		this.value = value;
    	}
    	
    	/** 
    	 * Returns the value of the node
    	 * 
    	 * Complexity - O(1)
    	 */
    	public int getValue() {
			return value;
		}

		/**
    	 * Sets input rightBrother as this HeapNode's right brother.
    	 * 
    	 *  Complexity - O(1)
    	 */
    	public void setRightBrother(HeapNode rightBrother) {
			this.rightBrother = rightBrother;
			
		}

    	/**
    	 * Sets input leftBrother as this HeapNode's left brother.
    	 * 
    	 *  Complexity - O(1)
    	 */
		public void setLeftBrother(HeapNode leftBrother) {
			this.leftBrother = leftBrother;
			
		}

		/**
    	 * Returns rightBrother.
    	 * 
    	 * Complexity - O(1)
    	 */
    	public HeapNode getRightBrother() {
			return rightBrother;
		}

		
		
		/**
		 * Links two binomial trees by making the tree with bigger key root the son of the smaller key root.
		 * returns the linked tree.
		 * 
		 * Complexity - O(1)
		 */
		public HeapNode link(HeapNode other) {
			
			//make sure both nodes are removed from any trees they might be in:
			leftBrother = null;
			rightBrother = null;
			other.leftBrother = null;
			other.rightBrother = null;
			
			//if the value of this node is smaller than the value of 'other', or the values are equal, and:
			//	1. this node's isMin field is true, or:
			//  2. other's isMin field is false
			//then make 'other' the leftMostSon of this node, and return this node.
			if (value < other.getValue() || (value == other.getValue() && (isMin || !other.isMin))) {
				rank++;//increase the rank of this node by 1
				
				//set the fields in order to make the link:
				other.setParent(this);
				if (leftMostSon != null) {
					other.setRightBrother(leftMostSon);
					leftMostSon.setLeftBrother(other);
				}
				leftMostSon = other;
				linkCounter++;
				return this;
			}
			
			//if the value of this node is bigger than the value of 'other', or the values are equal, and:
			//	1. this node's isMin field is false, and:
			//  2. other's isMin field is true
			//then make this node the leftMostSon of 'other', and return 'other'.
			else {
				return other.link(this);
			}
		}
		
		/**
		 * Sets input HeapNode to be this node's parent.
		 * 
		 * Complexity - O(1)
		 */
		private void setParent(HeapNode newParent) {
			parent = newParent;
		}

		/**
		 * Returns leftBrother
		 * 
		 * Complexity - O(1)
		 * 
		 */
		public HeapNode getLeftBrother() {
			return this.leftBrother;
		}

		/**
		 * Returns the rank of the HeapNode
		 * 
		 * Complexity - O(1)
		 * 
		 */
		public int getRank() {
			return this.rank;
		}
		
		/**
		 * Returns leftMostSon.
		 * 
		 * Complexity - O(1)
		 */
		public HeapNode getLeftMostSon() {
			return leftMostSon;
		}
    	
  	
    }

}